package SeqList;

public class SeqList<E> implements LinearList<E> { // 线性表的顺序存储实现（顺序表）
	protected Object[] element; // 地址连续的顺序存储空间，Object数组提供
	protected int n; // 顺序表元素个数（长度）
	private static final int MIN_CAPACITY = 16; // 定义顺序存储空间的最小容量

	public SeqList() {
		this(MIN_CAPACITY);
	}

	public SeqList(int length) {
		if (length < MIN_CAPACITY)
			length = MIN_CAPACITY;
		this.element = new Object[length];
		this.n = 0;
	}

	@Override
	public boolean isEmpty() {
		return this.n == 0;
	}

	@Override
	public int size() {
		return n;
	}

	@Override
	// 读取操作
	// 若0≤i<n，返回第i个元素；否则，返回null--- O(1)
	public E get(int i){ 
		if (i >= 0 && i < this.n)
			return (E) this.element[i];
		return null;
	}

	@Override
	// 若0≤i<n且x≠null，设置第i个元素为x；否则抛出序号越界异常或空对象异常---O(1)
	public void set(int i, E x) {
		//TODO
		if (i>=0 && i<n &&x!=null){
			this.element[i]=x;
		}else if (i<0||i>=n){
			throw new ArrayIndexOutOfBoundsException();
		}else if (x==null){
			throw new NullPointerException("元素为空");
		}
	}

	@Override
	// 顺序表的插入操作
	// 插入x为第i个元素，x!=null，返回插入成功true，失败false
	// x为null不能插入，插入失败
	// 对i容错，若i<0，则头插入；若i>长度，则尾插入
	// 对存储空间大小校验，若数组空间已满，则扩充顺序表的数组容量
	// 插入操作：将插入位置及之后的记录往后移动一个单元，待插入的数据放置到第i个元素的位置
	// 线性表长度加1
	// 时间复杂度：？
	public boolean insert(int i, E x) {
		//TODO
		if (i<0)i=0;	//若i<0，则头插入
		if (i>n)i=n;	//若i>长度，则尾插入

		// 对存储空间大小校验，若数组空间已满，则扩充顺序表的数组容量
		if(n==element.length){
			Object[] origin = this.element;
			this.element = new Object[this.element.length-2];
			for (int s=0;s<this.n;s++) {
				this.element[s] = origin[s];
			}
		}

		//x为null不能插入，插入失败
		if (x==null){
			return false;
		}

		for (int j = n-1;j>=i;j--){
			this.element[j+1]=this.element[j];
		}
		this.element[i]=x;
		n++;
		return true;
	}


	@Override
	public int insert(E x) { // 顺序表尾插入x元素，O(1)。成员方法重载
		this.insert(this.n, x); // 调用insert(i, x)方法
		return this.n;
	}
	

	@Override
	//顺序表的删除操作
    public E remove(int i) {           // 删除第i个元素，0≤i<n，返回被删除元素。若i越界，返回null。O(n)
        if(i>=0 && i<this.n)  {
            E x = (E)this.element[i];            // x中存储被删除元素
            for(int j=i; j<this.n-1; j++)
                this.element[j] = this.element[j+1];       // 元素前移一个位置
            this.element[this.n--]=null;         // 设置数组元素对象为空，释放原引用实例
            return x;                            // 返回x局部变量引用的对象，传递对象引用
        }
        return null;
    }

	@Override
	public void clear() //  删除所有元素
	{
		 // clear to let GC do its work
        for (int i = 0; i <= n; i++)
            element[i] = null;
        n = 0;
	}

	@Override
	// 顺序查找
    // 在this引用的顺序表中，顺序查找首个与key相等元素，返回元素序号i，0≤i<n；若查找不成功，则返回-1。
    // 顺序查找算法:O(n)
    public int search(E key) {
        //TODO
		for (int i = 0;i<n;i++){
			if (key.equals(element[i])){
				return i;
			}
		}
		return -1;                          // 空表或未找到时
    }

	@Override
	public boolean contains(E x) // 线性表中是否包含x元素
	{
		return this.search(x) != -1;
	}

	@Override
	public int remove(E key) // 删除值为key的记录
	{
		int i = this.search(key);
		if (i!=-1){
			this.remove(i);
		}
		return -1;	//没有值为key的记录
	}

	// 返回所有元素的描述字符串，形式为“[,]”。覆盖Object类的toString()方法
	// O(n)
	public String toString() {
		String str="[";
		if (this.n > 0)
			str += this.element[0].toString();
		for (int i = 1; i < this.n; i++) {
			str += ", " + this.element[i].toString();
			if (i % 15 == 0)
				str += "\n";
		}
		return str + "] ";
	}

	//删除所有关键字为key的数据元素，要求所有元素一次移动到位
	public void removeAll(E key){
		//定义两个指针分别指向现在需要修改的元素和下一个不是符合关键字的元素
		int now=0;
		int next = now+1;
		//进行循环直到第二个指针指向顺序表的末尾代表全部元素都已经处理完毕
		while (next<=n-1){
			if (key.equals(element[now])){
				while (key.equals(element[next])){
					next++;
				}
				element[now]=element[next];
			}
			now++;
			next++;
		}
		n=now-1;
	}

	//将第一个关键字为key的元素替换为x
	public void replaceFirst(E key,E x){
		int search = this.search(key);
		this.set(search,x);
	}

	//查找最后一个关键字为key的元素，返回其索引号
	public int searchLast(E key){
		for (int i = n-1;i>0;i--){
			if (key.equals(element[i])){
				return i+1;
			}
		}
		return -1;
	}
}
